Network security systems, often described as intrusion prevention systems (IPS) or intrusion detection systems (IDS) commonly employ both pattern matching, performed on a data stream represented by the packet payload, and the checking of headers to detect unwanted or undesirable digital signatures which may represent a security threat. Within the security rules used by such systems there are normally links between specific header values and the security thread content in the payload. For example, a pattern that may be significant (e.g. because it represents a potential threat) in one type of packet (e.g. a UDP packet) may not be important in another type (e.g. a TCP packet). When a pattern is detected but, having regard to its context, is not significant, it is generally termed a ‘false positive’. The production and elimination of false positive represent severe processing overhead in detection systems.
Accordingly it is not only necessary to detect the signature but also to ‘post-process’ the header to check for the header value qualifiers which confirm the ‘authenticity’ of a potential violation of security. In many cases there are several header fields which must match a specific value in order to determine that a genuine positive match has been obtained.
A deterministic finite automata (DFA), or deterministic finite state machine, as represented in graphical form, has a plurality of states each of which has an exit or transition dependent on an examination of the next ‘character’ or ‘byte’ in a string of characters that the DFA examines. In one practical form, each state of the DFA is represented by one or more locations in a memory, each location containing an identification of the pattern segment that must be detected by a comparator and an identification of the state to which the state machine will transition if there is a match on that character. Customarily, if there is no match, or under various other circumstances, the state machine reverts to an initial state.
In its simplest practical form, termed a single table machine, a DFA comprises, for each state, a multiplicity of locations showing the next state for each of the possible variations of an input character. Where, as is typical, an input character is a byte, a single table machine requires 256 locations, only one of which will identify a state other than the initial or default state. Thus the memory space required for a single table machine is in practice unmanageably large.
As will be described later, the present invention preferably employs a dual table machine. However, some elaborations of the present invention would greatly enlarge the memory space if a dual table machine is used and therefore the invention is not intended for implementation exclusively by a dual-table machine.